package dynamicProgramming.SingleSequenceProblem;

/**
 * @author zxc
 * @date 2023/01/21 08:58
 **/
/**
 * 题目 ：最少回文分割
 * 题目详述 ：
 * 给定一个字符串 s，请将 s 分割成一些子串，使每个子串都是回文串。
 * 返回符合要求的 最少分割次数 。
 *
 * 提示：
 * 1 <= s.length <= 2000
 * s 仅由小写英文字母组成
 */
public class MinCut {
    public static void main(String[] args) {
        minCut("leet");
    }
    /**
     * 思路 ：
     * 即，主字符串args（即，从最后一个字符串开始向前截取字符串）
     * （1）若是所截取的子字符串t不为回文的话，则继续向前截取字符串;
     * （2）若是所截去的子字符串t为回文字符串的话，则需要去求取（args - t）剩余字符串的最少回文分割次数;
     *
     * 状态转移方程 ：
     * 即，假设f(i+1)为长度为i+1的字符串S[0...i]的最少回文分割次数;
     * 若是后面截取的子字符串t[j...i]为回文字符串的话，即只需要去求取字符串s[0...j-1]的最少回文分割次数;
     * ===> f(i + 1) = f(j) + 1;
     * 需要注意的是，特殊情况 ：若是分割出的子字符串t[j...i] == S[0...i]的话，则不需要去增加分割次数;
     * @param s
     * @return
     */
    public static int minCut(String s) {
        // 由于redis[1]用来存储字符串中字符个数为1的最少分割次数;
        int[] redis = new int[s.length() + 1];
        // 若是字符串为一个字符，其必然为回文字符串（即，最少分割次数为0，不需要进行分割;）
        redis[1] = 0;
        // f(i) = f(j - 1) + 1;
        // 特殊情况 ：即，该字符串本身就为回文字符串，不需要进行分割;
        if(isPalindrome(s)){
            return 0;
        }
        // 外层for循环 ：来实现遍历所有子字符串S[0...j]，将S[0...j]子字符串的最少回文分割存储到对应的redis数组中;
        for(int i = 1 ; i < s.length() ; i++){
            int number = Integer.MAX_VALUE;
            // 内层for循环 ：遍历当前子字符串S[0...j]的所有可能分割，同时对比之下，获取到当前子字符串S[0...j]的最少回文分割
            for(int j = i + 1 ; j > 0 ; j--){
                // substring函数所截取的字符串[j- 1 ， i+ 1);
                String temp = s.substring(j - 1 , i + 1);
                // 若是所截取的子字符串t（子字符串是从尾部开始截取，）为回文字符串的话，即需要获取其最少的回文分割次数
                if(isPalindrome(temp)){
                    // 所截取子字符串t中的子字符串S[index...i]，由于截取的是从第index个字符到第i个字符所组成的字符串
                    // ===》 相互对比，获取当前子字符串S的最少分割次数;
                    number = Math.min(number , redis[j - 1] + (j == 1 ? 0 : 1));
                }
            }
            // 即，获取到当前子字符串S[0...i]的最少分割次数 && 同时，使用redis[i + 1]来保存当前子字符串的最少分割次数;
            redis[i + 1] = number;
        }
        // 直接返回redis数组中所保存的当前主字符串S中不同子字符串所对应的最少分割次数;
        return redis[s.length()];
    }
    // 判断当前字符串str是否为回文字符串
    private static boolean isPalindrome(String str) {
        int start = 0;
        int end = str.length() - 1;
        while(start < end){
            if(str.charAt(start++) != str.charAt(end--)){
                return false;
            }
        }
        return true;
    }
}
